using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0637. 二叉树的层平均值")]
    public class No0637_AverageOfLevels : AbsBaseTestItem
    {
        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }

        /*
        给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。
        提示：
            节点值的范围在32位有符号整数范围内。
        */

        public override void OnTest()
        {
            Assert.TestExe(AverageOfLevels,
                new TreeNode(3)
                {
                    left = new TreeNode(9),
                    right = new TreeNode(20)
                    {
                        left = new TreeNode(15),
                        right = new TreeNode(7),
                    }
                },
                new double[] { 3, 14.5, 11 });
        }

        public IList<double> AverageOfLevels(TreeNode root)
        {
            Dictionary<int, double> dicSum = new Dictionary<int, double>();
            Dictionary<int, int> dicCount = new Dictionary<int, int>();
            void UpNum(TreeNode node, int index)
            {
                if (node == null) return;
                dicSum[index] = dicSum.GetValueOrDefault(index, 0) + node.val;
                dicCount[index] = dicCount.GetValueOrDefault(index, 0) + 1;
                UpNum(node.left, index + 1);
                UpNum(node.right, index + 1);
            }
            UpNum(root, 0);
            double[] rlist = new double[dicSum.Keys.Count];
            foreach (int index in dicSum.Keys)
            {
                rlist[index] = dicSum[index] / dicCount[index];
            }
            return rlist;
        }
    }
}
